题解 P4135 【作诗】

发表于 | 更新于

$Description$

$N$个数，$M$组询问，每次问$[l,r]$中有多少个数出现正偶数次。

$Solution:$

考虑分块

先设$:f[i][j]$表示$i$块到$j$块的有多少个数出现正偶数次;

$sum[i][j]$表示前$i$块中，数值$j$的出现次数;

预处理$f$数组和$sum$数组,时间复杂度$O(n\sqrt n)$

处理询问时，设$res$为最终答案,$A$为询问左端点所在块，$B$为询问右端点所在块，先把$res$初值设为$f[A+1][B-1]$,然后处理两侧的不完整块.

对于一个值$j$,它在第$A+1$个块到第$B-1$个块中出现的次数就是$sum[B-1][j]-sum[A][j]$(类似于前缀和)

在处理不完整块的时候,若当前点的下标为$j$,那么只需要判断$++cnt[w[j]]+sum[B-1][w[j]]-sum[A][w[j]]$的奇偶性,并特判一下$0$变$1$的情况,然后更改$res$的值即可.

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 100007
#define S 323
using namespace std;

inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int size,num,w[N],ans,n,m,c,sum[S][N],cnt[N],belong[N],l[N],r[N],f[S][S];
void build(){
    size=sqrt(n);num=(n-1)/size+1;
    for (int i=1;i<=n;++i)belong[i]=(i-1)/size+1;
    for (int i=1;i<=num;++i)l[i]=(i-1)*size+1,r[i]=i*size;r[num]=n;
    for (int i=1;i<=num;++i){
        int res=0;
        for (int j=i;j<=num;++j){
            for (int k=l[j];k<=r[j];++k)
                if (!((++cnt[w[k]])&1))++res;
                else if (cnt[w[k]]!=1)--res;
            f[i][j]=res;
        }
        for (int j=i;j<=num;++j)
            for (int k=l[j];k<=r[j];++k)--cnt[w[k]];
    }
    memset(cnt,0,sizeof(cnt));
    for (int i=1;i<=n;++i){
        ++cnt[w[i]];
        if (i==r[belong[i]])
            memcpy(sum[belong[i]],cnt,sizeof(sum[belong[i]]));
    }
}
inline int calc(int l,int r,int w){
    return (l<r)?(sum[r-1][w]-sum[l][w]):0;
}
int query(int x,int y){
    x=(x+ans)%n+1,y=(y+ans)%n+1;
    if (x>y)swap(x,y);
    int A=belong[x],B=belong[y],res=f[A+1][B-1];
    for (int i=x;i<=min(y,r[A]);++i){
        if (!((++cnt[w[i]]+calc(A,B,w[i]))&1))++res;
        else if (cnt[w[i]]+calc(A,B,w[i])!=1)--res;
    }
    if (A!=B){
        for (int i=l[B];i<=y;++i){
            if (!((++cnt[w[i]]+calc(A,B,w[i]))&1))++res;
            else if (cnt[w[i]]+calc(A,B,w[i])!=1)--res;
        }
        for (int i=l[B];i<=y;++i)--cnt[w[i]];
    }
    for (int i=x;i<=min(y,r[A]);++i)--cnt[w[i]];
    return res;
}
signed main(){
    n=read(),c=read(),m=read();
    for (int i=1;i<=n;++i)w[i]=read();
    build();
    memset(cnt,0,sizeof(cnt));
    for (int i=1;i<=m;++i)
        printf("%d\n",ans=query(read(),read()));
    return 0;
}